package com.chj.jz.dp.class02;

// https://www.lintcode.com/problem/paint-house/description
public class Code02_PaintHouse {
	/**
	 * @param costs:
	 *            n x 3 cost matrix
	 * @return: An integer, the minimum cost to paint all houses
	 */
	public static int minCost(int[][] costs) {
		// write your code here
		int n = costs.length;
		if (n == 0) {
			return 0;
		}

		int[][] f = new int[n + 1][3];
		f[0][0] = f[0][1] = f[0][2] = 0;
		int i, j, k;
		for (i = 1; i <= n; i++) {
			for (j = 0; j < 3; j++) {
				f[i][j] = Integer.MAX_VALUE;
				for (k = 0; k < 3; k++) {
					if (j != k) {
						f[i][j] = Math.min(f[i][j], f[i - 1][k] + costs[i - 1][j]);
					}
				}
			}
		}

		return Math.min(f[n][0], Math.min(f[n][1], f[n][2]));
	}

	public static void main(String[] args) {
		{
			int[][] arr = new int[][] { { 14, 2, 11 }, { 11, 14, 5 }, { 14, 3, 10 } };
			System.out.println(minCost(arr));
		}
		{
			int[][] arr = new int[][] { { 1, 2, 3 }, { 1, 4, 6 } };
			System.out.println(minCost(arr));
		}
	}
}
